package com.leetcode.partition1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/7/30 8:54
 */
public class LC22括号生成 {

    public static List<String> generateParenthesis(int n) {
        List<String> answer = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        sb.append('(');
        backtracking(1, 0, n, sb, answer);
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    private static void backtracking(int leftParenthesis, int rightParenthesis, int n, StringBuilder sb, List<String> answer) {
        //任何时候右括号都不能多余左括号
        if (rightParenthesis > leftParenthesis) return;
        //只有当左括号数等于右括号数且和指定括号对数相等，才进行结果集的添加
        if (leftParenthesis == rightParenthesis && leftParenthesis == n) {
            answer.add(sb.toString());
            return;
        }
        //只有左括号数量小于n时，才能对左括号进行添加
        if (leftParenthesis < n) {
            sb.append('(');
            backtracking(leftParenthesis + 1, rightParenthesis, n, sb, answer);
            sb.deleteCharAt(sb.length() - 1);
        }
        //只有右括号数量小于左括号数，才能添加右括号
        if (rightParenthesis < leftParenthesis) {
            sb.append(')');
            backtracking(leftParenthesis, rightParenthesis + 1, n, sb, answer);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
